数据结构

名词解释

• 数据结构：可以容纳数据的结构（静态），面向存储
• 算法：对数据结构进行处理的方法（动态），面向运算

线性数据结构-数组

数组特性

1. 存储在物理空间上是连续的；
2. 底层的数组长度是不可变的；
3. 数组的变量，指向了数组第一个元素的位置。

var arr = [1, 2, 3, 4, 5, 7, 8]

优点：

• 查询性能好。指定查询某个位置

系统偏移查询：arr[1], arr[2], arr[3] （通过系统偏移查询的方式性能最好）

缺点：

• 如果数组比较大，当系统空间碎片较多的时候，容易存不下；
• 难以添加和删除。

添加或删除会造成数组扩容：

[1, 2, 3, 4, 5, 7, 8, 9, null, null, null, null, null, null, null]

初始指定长度，使性能达到最高

var arr1 = [1, 2, 3, 4, 5];  // 固定内容情况下
var arr2 = new Array(10);  // 不固定内容情况下

线性数据结构-链表

链表特性

1. 空间不是连续的；
2. 每存放一个值，都会多开销一个引用空间。

var a = {1: b}  // 链表之间的关系不是嵌套，而是引用
var b = {2: 'string'}

没一个节点，都认为自己是根节点

优点：

• 只要内存足够大，就能存的下，不用担心空间碎片的问题
• 链表的添加和删除非常的容易

缺点：

• 查询速度慢（指定查询某个位置）
• 链表每一个节点都需要创建一个指向 next 的引用，浪费一些空间

节点数据越多，这部分多开销的内存影响越少（一人点火锅与多人点火锅的区别，人越多个人开销越少）

链表创建

function Node (value) {
    this.value = value;
    this.next = null;
}
var a = new Node(1);
var b = new Node(2);
var c = new Node(3);
var d = new Node(4);

a.next = b;
b.next = c;
c.next = d;
d.next = null;

console.log(a.value);
console.log(a.next.value);

循环遍历

function bianLink (root) {
    var temp = root;
    while (true) {
        if (temp != null) {
            console.log(temp.value);
        } else {
            break;
        }
        temp = temp.next;
    }    
}
bianLink(a);  //--> 1 2 3 4

递归遍历

// 分治法
function recursion (root) {
    if (root == null) return;
    console.log(root.value);
    recursion(root.next);
}
recursion(a);  //--> 1 2 3 4

链表逆置

// 1 2 3 4 5 6 7
function nizhi (root) {
    if (root.next.next == null) {
        root.next.next = root;
        return root.next;
    } else {
        var result = nizhi(root.next);
        root.next.next = root;
        root.next = null;
        return result;
    }
}
var newRoot = nizhi(a);
bianLink(newRoot);  //--> 4 3 2 1

双向链表

• 优点：无论给出哪一个节点，都能对整个链表进行遍历
• 缺点：多耗费一个引用的空间，而且构建双向链表比较复杂

function Node (value) {
    this.value = value;
    this.next = null;
    this.pre = null;
}

var node1 = new Node(1);
var node2 = new Node(2);
var node3 = new Node(3);
var node4 = new Node(4);
var node5 = new Node(5);

node1.next = node2;
node2.pre = node1;
node2.next = node3;
node3.pre = node2;
node3.next = node4;
node4.pre = node3;
node4.next = node5;
node5.pre = node4;

二维数组

[ [1, 2], [1, 2], [1, 2], [1, 2] ]

var arr = new Array(4);
for (var i = 0; i < arr.length; i ++) {
    arr[i] = new Array(8);
}

console.log(arr);  //--> [Array(8), Array(8), Array(8), Array(8)]

二维拓扑结构 / 图

就像是人与人之间的血缘关系，剪不断，理还乱。不受距离、长度等影响

function Node (value) {
    this.value = value;
    this.neighbor = [];
}

var a = new Node('a');
var b = new Node('b');
var c = new Node('c');
var d = new Node('d');
var e = new Node('e');
a.neighbor.push(b);
a.neighbor.push(d);
a.neighbor.push(e);
b.neighbor.push(c);
b.neighbor.push(e);
c.neighbor.push(a);
c.neighbor.push(d);

console.log(a);  //--> 
/* {value: 'a',
    neighbor: [
        Node { value: 'b', neighbor: [Array] },
        Node { value: 'd', neighbor: [] },
        Node { value: 'e', neighbor: [] }
    ]
} */

有向无环图 / 树形结构

只有一个根节点，并且没有回路

• 根节点：
• 叶子节点：下面没有其他节点了
• 节点：既不是根节点，也不是叶子节点的普通节点
• 度：树形机构中最多叉的节点的个数
• 深度：树形结构的层数

1. 二叉树：度不能超过两个；
2. 满二叉树：每个节点都有两个度，所有叶子节点都在最底层；
3. 完全二叉树：
   • 国内定义：叶子节点都在最后一层或倒数第二层，叶子节点都向左聚拢；
   • 国际定义：叶子节点都在最后一层或倒数第二层，叶子节点为两个或一个；
4. 子树：每一个节点或叶子节点，都是一颗子树的根节点（一个叶子节点也是子树）。